#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_LENGTH = 100000;
int n;
string word;
int order[MAX_LENGTH];
char wordPtr[MAX_LENGTH];
bool used[MAX_LENGTH];
string lastWord;
char lastWordPtr[MAX_LENGTH];

bool cmp(const char x, const char y) {
	char lx = x, ly = y;
	if ('A'<=x && x<='Z') lx = x - 'A' + 'a';
	if ('A'<=y && y<='Z') ly = y - 'A' + 'a';
	if (lx == ly) return x < y;
	else return lx < ly;
}

bool myLess(string a, string b){
	for (int i=0; i<min(a.length(), b.length()); ++i) {
		if (cmp(a[i], b[i])) return true;
		if (cmp(b[i], a[i])) return false;
	}
	return a.length() < b.length();
}

void travel(int pos) {
	string newWord;
	for (int i=0; i<pos; ++i)
		lastWordPtr[i] = wordPtr[order[i]];
	newWord = string(lastWordPtr, 0, word.length());
	if (myLess(newWord, lastWord)) return;

	if (pos == word.length()) {
		if (lastWord == newWord) return;
		cout << newWord << endl;
		lastWord = newWord;
		return;
	}
	bool firstblood = true;
	for (int i=0; i<word.length(); ++i) {
		if (used[i]) continue;
		if (i>0 && wordPtr[i] == wordPtr[i-1]) {
			if (!firstblood) continue;
			else firstblood = false;
		}
		else firstblood = true;
		order[pos] = i;
		used[i] = true;
		travel(pos+1);
		used[i] = false;
	}
}

int main(void)
{
	cin >> n;
	for (int testcase = 0; testcase < n; ++testcase) {
		cin >> word;
		memset(wordPtr, 0, MAX_LENGTH);
		memcpy(wordPtr, word.c_str(), word.length());
		sort(wordPtr, wordPtr+word.length(), cmp);
		lastWord = "";
		travel(0);
	}
	return 0;
}
